package top.minuy.structure.graph.network;

import top.minuy.structure.graph.representations.table.WeightedGraph;
import top.minuy.structure.graph.representations.table.WeightedGraphDynamic;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 网络中的最大流
 * Ford-Fulkerson 思想
 * Edmonds-Karp 算法
 *
 * @author Minuy
 * @time 9:02
 * @date 2021/11/28
 */
public class MaxFlow {
    private WeightedGraphDynamic rg; // 残量图
    private WeightedGraph g; // 要处理的图
    private int s, t; // 流源点和流终点
    private int maxFlow; // 最大流

    public MaxFlow(WeightedGraph g, int s, int t) {
        this.g = g;
        if (!g.isDirected()) {
            throw new IllegalArgumentException("MaxFlow only works in directed graph.");
        }

        g.validateVertex(s);
        g.validateVertex(t);
        if (s == t) {
            throw new IllegalArgumentException("The s and the t should be different.");
        }
        this.s = s;
        this.t = t;

        rg = creatResidualGraph();
        maxFlow = 0;

        while (true) {
            // 找一条增广路径
            List<Integer> augPath = getAugmentingPath();
            if (augPath.size() == 0) { // 如果不能找到路径了
                break; // 结束
            }

            // System.out.println("----->"+augPath);

            // 找出路径中的最小值
            int minFlow = rg.getWeight(augPath.get(0), augPath.get(1));
            for (int i = 1; i < augPath.size(); i++) {
                minFlow = Math.min(rg.getWeight(augPath.get(i - 1), augPath.get(i)), minFlow);
            }

            //更新最大流数据
            maxFlow += minFlow;

            // 更新残量图
            for (int i = 1; i < augPath.size(); i++) {
                int v = augPath.get(i - 1);
                int w = augPath.get(i);

                // .  s...->...t
                // .  <- : 残量，初始为容量（原图的权）
                // .  -> : 流量，初始为零
                // .  有（原图中存在）：消耗残量，增加流量
                // .  无（原图中不在）：消耗流量，增加残量

                /*if (g.hasEdge(v, w)) {
                    // 有：消耗残量，增加流量
                    rg.setWeight(v, w, rg.getWeight(v, w) + minFlow); // 流量
                    rg.setWeight(w, v, rg.getWeight(w, v) - minFlow); // 残量
                } else {
                    // 无：消耗流量，增加残量
                    rg.setWeight(v, w, rg.getWeight(v, w) + minFlow); // 残量
                    rg.setWeight(w, v, rg.getWeight(w, v) - minFlow); // 流量
                }*/
/*
                // 正向增加，反向减少
                // 可以这么理解：增广路径走的不管是流量还是残量，
                // 正向都是增加（以流量来理解），反向都是减少（以流量来理解）
                rg.setWeight(v, w, rg.getWeight(v, w) + minFlow);
                rg.setWeight(w, v, rg.getWeight(w, v) - minFlow);

 */

                // 后来发现这才是对的
                // 怎么理解？
                // 正向消耗，因为到0时就不能走了，所以是减
                // 反之反向就是加
                rg.setWeight(v, w, rg.getWeight(v, w) - minFlow);
                rg.setWeight(w, v, rg.getWeight(w, v) + minFlow);
            }

            // System.out.println(minFlow);

            // System.out.println(rg);
        }

    }

    /**
     * 查询某边上的流量
     *
     * @param v 边开始的顶点v
     * @param w 边结束的顶点w
     * @return int 这条边上的流量
     * @author Minuy
     * @date 2021/11/29 14:12
     */
    public int flow(int v, int w) {
        if (g.hasEdge(v, w)) {
            return rg.getWeight(v, w);
        }
        throw new IllegalArgumentException(String.format("The graph not has edge %d->%d.", v, w));
    }

    /**
     * 获取计算出的最大流量
     *
     * @return int 最大流量
     * @author Minuy
     * @date 2021/11/29 14:10
     */
    public int maxFlow() {
        return maxFlow;
    }

    /**
     * 得到增广路径
     *
     * @return List<Integer> 返回一条曾广路径
     * @author Minuy
     * @date 2021/11/29 13:32
     */
    private List<Integer> getAugmentingPath() {
        int[] pre = new int[rg.V()];
        for (int i = 0; i < pre.length; i++) {
            pre[i] = -1;
        }

        ArrayList<Integer> queue = new ArrayList<>();
        int v = s;
        queue.add(v);
        pre[v] = v;
        while (!queue.isEmpty()) {
            v = queue.remove(0);

            if (v == t) { // 到目标点了可以提前结束
                break;
            }

            for (String ws : rg.adj(v)) {
                int w = Integer.parseInt(ws);
                if (pre[w] == -1) { // 如果顶点在本次遍历中未被访问
                    if (rg.getWeight(v, ws) > 0) { // 这条路还有 残量/流量
                        queue.add(w);
                        pre[w] = v;
                    }
                }
            }
        }

        List<Integer> path = new ArrayList<>();

        if (pre[t] != -1) { // 如果到过了目的地
            // 找出路径
            int cur = t;
            while (cur != s) {
                path.add(cur);
                cur = pre[cur];
            }
            path.add(s);

            Collections.reverse(path);
        }

        return path;
    }

    /**
     * 创建残量图
     *
     * @return WeightedGraphDynamic 残量图
     * @author Minuy
     * @date 2021/11/29 14:11
     */
    private WeightedGraphDynamic creatResidualGraph() {
        WeightedGraphDynamic rg = new WeightedGraphDynamic(true);

        // 复制顶点
        for (int v = 0; v < g.V(); v++) {
            rg.addVertex(v);
        }

        // 复制边，构建 流量/残量
        for (int v = 0; v < g.V(); v++) {
            for (int w : g.adj(v)) {
                if (rg.hasEdge(v, w) || rg.hasEdge(w, v)) {
                    throw new IllegalArgumentException("Parallel edge or cycle has detection.");
                } else {
                    // v -> w
                    int residual = g.getWeight(v, w); // 残量，剩余的容量
                    int flow = 0; // 流量，已经使用的容量

                    rg.addEdge(v, w, residual);
                    rg.addEdge(w, v, flow);
                }
            }
        }

        return rg;
    }

}
